package leetcode.search;

import leetcode.sort.SelectSort;

import java.util.*;

/**
 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

 输入：nums = [1,2,3]
 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 */
public class Permute46 {
    public List<List<Integer>> permute(int[] nums) {
        ArrayList<List<Integer>> res = new ArrayList<>();
//        permute(nums,0,res);

        boolean[] used = new boolean[nums.length];
        permute2(used,nums,0,res,new LinkedList<>());
        return  res;

    }


    private void permute(int []nums, int index, ArrayList<List<Integer>> res){
        if(index == nums.length-1){
            ArrayList<Integer> list = new ArrayList<>();
            for (int num : nums) {
                list.add(num);
            }
            res.add(list);
            return;
        }
            for (int i = index; i < nums.length; i++) {
                swap(nums,i,index);
                permute(nums,index+1,res);
                swap(nums,i,index);
            }
    }

    private void permute2(boolean []used,int []nums, int index, ArrayList<List<Integer>> res,LinkedList <Integer> path){
        if(index == nums.length){
            res.add(new ArrayList<>(path));
        }
        for (int i = 0; i < nums.length; i++) {
            if(used[i])
                continue;

            path.add(nums[i]);
            used[i] = true;
            permute2(used,nums,index+1,res,path);
            used[i] = false;
            path.removeLast();
        }
    }


    private void swap(int []nums,int i,int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}